#include "rtree.h"
#include "index_manager.h"
#include "../memory/memory_manager.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <float.h>

static const uint32_t DEFAULT_MAX_ENTRIES = RTREE_MAX_CHILDREN;
static const uint32_t DEFAULT_MIN_ENTRIES = RTREE_MIN_CHILDREN;

void rtree_rect_init(rtree_rect_t* rect, uint8_t dimensions) {
    if (!rect || dimensions == 0 || dimensions > RTREE_MAX_DIMENSIONS) return;
    
    rect->dimensions = dimensions;
    for (uint8_t i = 0; i < dimensions; i++) {
        rect->min[i] = DBL_MAX;
        rect->max[i] = -DBL_MAX;
    }
}

void rtree_rect_from_point(rtree_rect_t* rect, const rtree_point_t* point) {
    if (!rect || !point) return;
    
    rect->dimensions = point->dimensions;
    for (uint8_t i = 0; i < point->dimensions; i++) {
        rect->min[i] = point->coords[i];
        rect->max[i] = point->coords[i];
    }
}

bool rtree_rect_intersects(const rtree_rect_t* rect1, const rtree_rect_t* rect2) {
    if (!rect1 || !rect2 || rect1->dimensions != rect2->dimensions) {
        return false;
    }
    
    for (uint8_t i = 0; i < rect1->dimensions; i++) {
        if (rect1->max[i] < rect2->min[i] || rect1->min[i] > rect2->max[i]) {
            return false;
        }
    }
    return true;
}

bool rtree_rect_contains(const rtree_rect_t* outer, const rtree_rect_t* inner) {
    if (!outer || !inner || outer->dimensions != inner->dimensions) {
        return false;
    }
    
    for (uint8_t i = 0; i < outer->dimensions; i++) {
        if (outer->min[i] > inner->min[i] || outer->max[i] < inner->max[i]) {
            return false;
        }
    }
    return true;
}

bool rtree_rect_contains_point(const rtree_rect_t* rect, const rtree_point_t* point) {
    if (!rect || !point || rect->dimensions != point->dimensions) {
        return false;
    }
    
    for (uint8_t i = 0; i < rect->dimensions; i++) {
        if (point->coords[i] < rect->min[i] || point->coords[i] > rect->max[i]) {
            return false;
        }
    }
    return true;
}

double rtree_rect_area(const rtree_rect_t* rect) {
    if (!rect) return 0.0;
    
    double area = 1.0;
    for (uint8_t i = 0; i < rect->dimensions; i++) {
        double extent = rect->max[i] - rect->min[i];
        if (extent < 0.0) return 0.0;
        area *= extent;
    }
    return area;
}

double rtree_rect_margin(const rtree_rect_t* rect) {
    if (!rect) return 0.0;
    
    double margin = 0.0;
    for (uint8_t i = 0; i < rect->dimensions; i++) {
        margin += rect->max[i] - rect->min[i];
    }
    return margin;
}

void rtree_rect_union(rtree_rect_t* result, const rtree_rect_t* rect1, const rtree_rect_t* rect2) {
    if (!result || !rect1 || !rect2) return;
    
    uint8_t dimensions = rect1->dimensions < rect2->dimensions ? 
                        rect1->dimensions : rect2->dimensions;
    result->dimensions = dimensions;
    
    for (uint8_t i = 0; i < dimensions; i++) {
        result->min[i] = rect1->min[i] < rect2->min[i] ? rect1->min[i] : rect2->min[i];
        result->max[i] = rect1->max[i] > rect2->max[i] ? rect1->max[i] : rect2->max[i];
    }
}

double rtree_rect_distance(const rtree_rect_t* rect1, const rtree_rect_t* rect2) {
    if (!rect1 || !rect2 || rect1->dimensions != rect2->dimensions) {
        return DBL_MAX;
    }
    
    double distance_squared = 0.0;
    for (uint8_t i = 0; i < rect1->dimensions; i++) {
        double d = 0.0;
        if (rect1->max[i] < rect2->min[i]) {
            d = rect2->min[i] - rect1->max[i];
        } else if (rect2->max[i] < rect1->min[i]) {
            d = rect1->min[i] - rect2->max[i];
        }
        distance_squared += d * d;
    }
    
    return sqrt(distance_squared);
}

double rtree_point_distance(const rtree_point_t* point1, const rtree_point_t* point2) {
    if (!point1 || !point2 || point1->dimensions != point2->dimensions) {
        return DBL_MAX;
    }
    
    double distance_squared = 0.0;
    for (uint8_t i = 0; i < point1->dimensions; i++) {
        double d = point1->coords[i] - point2->coords[i];
        distance_squared += d * d;
    }
    
    return sqrt(distance_squared);
}

void rtree_point_init(rtree_point_t* point, uint8_t dimensions) {
    if (!point || dimensions == 0 || dimensions > RTREE_MAX_DIMENSIONS) return;
    
    point->dimensions = dimensions;
    for (uint8_t i = 0; i < dimensions; i++) {
        point->coords[i] = 0.0;
    }
}

bool rtree_point_equals(const rtree_point_t* point1, const rtree_point_t* point2) {
    if (!point1 || !point2 || point1->dimensions != point2->dimensions) {
        return false;
    }
    
    for (uint8_t i = 0; i < point1->dimensions; i++) {
        if (fabs(point1->coords[i] - point2->coords[i]) > DBL_EPSILON) {
            return false;
        }
    }
    return true;
}

rtree_node_t* rtree_node_create(memory_manager_t* memory_mgr, rtree_node_type_t type,
                               uint32_t max_entries, uint8_t dimensions) {
    if (!memory_mgr || max_entries == 0 || dimensions == 0 || 
        dimensions > RTREE_MAX_DIMENSIONS) {
        return NULL;
    }
    
    rtree_node_t* node = mm_alloc(memory_mgr, sizeof(rtree_node_t), MEM_TYPE_INDEX_BUFFER);
    if (!node) return NULL;
    
    memset(node, 0, sizeof(rtree_node_t));
    node->type = type;
    node->is_root = false;
    node->entry_count = 0;
    node->max_entries = max_entries;
    node->memory_mgr = memory_mgr;
    node->level = 0;
    
    rtree_rect_init(&node->mbr, dimensions);
    
    node->entries = mm_alloc(memory_mgr, sizeof(rtree_entry_t) * max_entries,
                            MEM_TYPE_INDEX_BUFFER);
    if (!node->entries) {
        mm_free(memory_mgr, node);
        return NULL;
    }
    memset(node->entries, 0, sizeof(rtree_entry_t) * max_entries);
    
    if (pthread_rwlock_init(&node->rwlock, NULL) != 0) {
        mm_free(memory_mgr, node->entries);
        mm_free(memory_mgr, node);
        return NULL;
    }
    
    return node;
}

void rtree_node_destroy(rtree_node_t* node) {
    if (!node) return;
    
    pthread_rwlock_wrlock(&node->rwlock);
    
    for (uint32_t i = 0; i < node->entry_count; i++) {
        if (node->entries[i].value) {
            mm_free(node->memory_mgr, node->entries[i].value);
        }
        if (node->type == RTREE_NODE_INTERNAL && node->entries[i].child) {
            rtree_node_destroy(node->entries[i].child);
        }
    }
    
    if (node->entries) {
        mm_free(node->memory_mgr, node->entries);
    }
    
    pthread_rwlock_unlock(&node->rwlock);
    pthread_rwlock_destroy(&node->rwlock);
    
    mm_free(node->memory_mgr, node);
}

void rtree_node_update_mbr(rtree_node_t* node) {
    if (!node || node->entry_count == 0) return;
    
    rtree_rect_init(&node->mbr, node->entries[0].mbr.dimensions);
    
    for (uint32_t i = 0; i < node->entry_count; i++) {
        if (i == 0) {
            node->mbr = node->entries[i].mbr;
        } else {
            rtree_rect_union(&node->mbr, &node->mbr, &node->entries[i].mbr);
        }
    }
}

index_result_t rtree_node_insert_entry(rtree_node_t* node, rtree_entry_t* entry) {
    if (!node || !entry || node->entry_count >= node->max_entries) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    pthread_rwlock_wrlock(&node->rwlock);
    
    node->entries[node->entry_count] = *entry;
    node->entry_count++;
    
    rtree_node_update_mbr(node);
    
    pthread_rwlock_unlock(&node->rwlock);
    return INDEX_SUCCESS;
}

index_result_t rtree_node_delete_entry(rtree_node_t* node, uint32_t pos) {
    if (!node || pos >= node->entry_count) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    pthread_rwlock_wrlock(&node->rwlock);
    
    if (node->entries[pos].value) {
        mm_free(node->memory_mgr, node->entries[pos].value);
    }
    
    for (uint32_t i = pos; i < node->entry_count - 1; i++) {
        node->entries[i] = node->entries[i + 1];
    }
    
    memset(&node->entries[node->entry_count - 1], 0, sizeof(rtree_entry_t));
    node->entry_count--;
    
    if (node->entry_count > 0) {
        rtree_node_update_mbr(node);
    } else {
        rtree_rect_init(&node->mbr, node->mbr.dimensions);
    }
    
    pthread_rwlock_unlock(&node->rwlock);
    return INDEX_SUCCESS;
}

double rtree_entry_area_enlargement(rtree_entry_t* entry, const rtree_rect_t* rect) {
    if (!entry || !rect) return DBL_MAX;
    
    double original_area = rtree_rect_area(&entry->mbr);
    
    rtree_rect_t union_rect;
    rtree_rect_union(&union_rect, &entry->mbr, rect);
    double union_area = rtree_rect_area(&union_rect);
    
    return union_area - original_area;
}

int rtree_choose_subtree(rtree_node_t* node, const rtree_rect_t* rect) {
    if (!node || !rect || node->entry_count == 0) return -1;
    
    int best_index = 0;
    double min_enlargement = rtree_entry_area_enlargement(&node->entries[0], rect);
    double min_area = rtree_rect_area(&node->entries[0].mbr);
    
    for (uint32_t i = 1; i < node->entry_count; i++) {
        double enlargement = rtree_entry_area_enlargement(&node->entries[i], rect);
        double area = rtree_rect_area(&node->entries[i].mbr);
        
        if (enlargement < min_enlargement || 
            (enlargement == min_enlargement && area < min_area)) {
            best_index = i;
            min_enlargement = enlargement;
            min_area = area;
        }
    }
    
    return best_index;
}

rtree_index_t* rtree_create(memory_manager_t* memory_mgr, uint8_t dimensions) {
    if (!memory_mgr || dimensions == 0 || dimensions > RTREE_MAX_DIMENSIONS) {
        return NULL;
    }
    
    rtree_index_t* rtree = mm_alloc(memory_mgr, sizeof(rtree_index_t), MEM_TYPE_INDEX_BUFFER);
    if (!rtree) return NULL;
    
    memset(rtree, 0, sizeof(rtree_index_t));
    rtree->memory_mgr = memory_mgr;
    rtree->dimensions = dimensions;
    rtree->max_entries = DEFAULT_MAX_ENTRIES;
    rtree->min_entries = DEFAULT_MIN_ENTRIES;
    rtree->allow_duplicates = true;
    rtree->height = 0;
    rtree->total_entries = 0;
    
    if (pthread_rwlock_init(&rtree->tree_lock, NULL) != 0) {
        mm_free(memory_mgr, rtree);
        return NULL;
    }
    
    rtree->root = rtree_node_create(memory_mgr, RTREE_NODE_LEAF, 
                                   rtree->max_entries, dimensions);
    if (!rtree->root) {
        pthread_rwlock_destroy(&rtree->tree_lock);
        mm_free(memory_mgr, rtree);
        return NULL;
    }
    rtree->root->is_root = true;
    rtree->height = 1;
    
    return rtree;
}

void rtree_destroy(rtree_index_t* rtree) {
    if (!rtree) return;
    
    pthread_rwlock_wrlock(&rtree->tree_lock);
    
    if (rtree->root) {
        rtree_node_destroy(rtree->root);
    }
    
    pthread_rwlock_unlock(&rtree->tree_lock);
    pthread_rwlock_destroy(&rtree->tree_lock);
    
    mm_free(rtree->memory_mgr, rtree);
}

static rtree_node_t* rtree_find_leaf(rtree_index_t* rtree, const rtree_rect_t* rect) {
    rtree_node_t* current = rtree->root;
    
    while (current && current->type == RTREE_NODE_INTERNAL) {
        pthread_rwlock_rdlock(&current->rwlock);
        
        int best_index = rtree_choose_subtree(current, rect);
        if (best_index < 0) {
            pthread_rwlock_unlock(&current->rwlock);
            break;
        }
        
        rtree_node_t* next = current->entries[best_index].child;
        pthread_rwlock_unlock(&current->rwlock);
        current = next;
    }
    
    return current;
}

static rtree_entry_t* rtree_create_entry(memory_manager_t* memory_mgr,
                                        const rtree_rect_t* rect,
                                        const void* value, size_t value_size) {
    rtree_entry_t* entry = mm_alloc(memory_mgr, sizeof(rtree_entry_t), MEM_TYPE_INDEX_BUFFER);
    if (!entry) return NULL;
    
    memset(entry, 0, sizeof(rtree_entry_t));
    entry->mbr = *rect;
    entry->child = NULL;
    entry->record_id = 0;
    
    if (value && value_size > 0) {
        entry->value = mm_alloc(memory_mgr, value_size, MEM_TYPE_INDEX_BUFFER);
        if (!entry->value) {
            mm_free(memory_mgr, entry);
            return NULL;
        }
        memcpy(entry->value, value, value_size);
        entry->value_size = value_size;
    }
    
    return entry;
}

rtree_node_t* rtree_node_split(rtree_node_t* node, rtree_entry_t* new_entry) {
    if (!node || !new_entry) return NULL;
    
    uint32_t split_index = node->max_entries / 2;
    rtree_node_t* new_node = rtree_node_create(node->memory_mgr, node->type,
                                              node->max_entries, node->mbr.dimensions);
    if (!new_node) return NULL;
    
    pthread_rwlock_wrlock(&node->rwlock);
    
    for (uint32_t i = split_index; i < node->entry_count; i++) {
        new_node->entries[new_node->entry_count++] = node->entries[i];
        memset(&node->entries[i], 0, sizeof(rtree_entry_t));
    }
    
    node->entry_count = split_index;
    new_node->level = node->level;
    new_node->parent = node->parent;
    
    if (split_index == 0) {
        rtree_node_insert_entry(new_node, new_entry);
    } else {
        rtree_node_insert_entry(node, new_entry);
    }
    
    rtree_node_update_mbr(node);
    rtree_node_update_mbr(new_node);
    
    pthread_rwlock_unlock(&node->rwlock);
    
    return new_node;
}

index_result_t rtree_insert(rtree_index_t* rtree, const rtree_rect_t* rect,
                           const void* value, size_t value_size) {
    if (!rtree || !rect || rect->dimensions != rtree->dimensions) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    pthread_rwlock_wrlock(&rtree->tree_lock);
    
    rtree->inserts++;
    
    rtree_node_t* leaf = rtree_find_leaf(rtree, rect);
    if (!leaf) {
        pthread_rwlock_unlock(&rtree->tree_lock);
        return INDEX_ERROR_OUT_OF_MEMORY;
    }
    
    rtree_entry_t* new_entry = rtree_create_entry(rtree->memory_mgr, rect, value, value_size);
    if (!new_entry) {
        pthread_rwlock_unlock(&rtree->tree_lock);
        return INDEX_ERROR_OUT_OF_MEMORY;
    }
    
    if (leaf->entry_count < leaf->max_entries) {
        index_result_t result = rtree_node_insert_entry(leaf, new_entry);
        mm_free(rtree->memory_mgr, new_entry);
        
        if (result == INDEX_SUCCESS) {
            rtree->total_entries++;
        }
        
        pthread_rwlock_unlock(&rtree->tree_lock);
        return result;
    }
    
    rtree_node_t* new_leaf = rtree_node_split(leaf, new_entry);
    if (!new_leaf) {
        if (new_entry->value) {
            mm_free(rtree->memory_mgr, new_entry->value);
        }
        mm_free(rtree->memory_mgr, new_entry);
        pthread_rwlock_unlock(&rtree->tree_lock);
        return INDEX_ERROR_OUT_OF_MEMORY;
    }
    
    mm_free(rtree->memory_mgr, new_entry);
    rtree->splits++;
    
    if (leaf->is_root) {
        rtree_node_t* new_root = rtree_node_create(rtree->memory_mgr,
                                                  RTREE_NODE_INTERNAL,
                                                  rtree->max_entries,
                                                  rtree->dimensions);
        if (!new_root) {
            pthread_rwlock_unlock(&rtree->tree_lock);
            return INDEX_ERROR_OUT_OF_MEMORY;
        }
        
        new_root->is_root = true;
        new_root->level = leaf->level + 1;
        leaf->is_root = false;
        new_leaf->parent = new_root;
        leaf->parent = new_root;
        
        rtree_entry_t left_entry = {0};
        left_entry.mbr = leaf->mbr;
        left_entry.child = leaf;
        
        rtree_entry_t right_entry = {0};
        right_entry.mbr = new_leaf->mbr;
        right_entry.child = new_leaf;
        
        rtree_node_insert_entry(new_root, &left_entry);
        rtree_node_insert_entry(new_root, &right_entry);
        
        rtree->root = new_root;
        rtree->height++;
    }
    
    rtree->total_entries++;
    
    pthread_rwlock_unlock(&rtree->tree_lock);
    return INDEX_SUCCESS;
}

index_result_t rtree_insert_point(rtree_index_t* rtree, const rtree_point_t* point,
                                 const void* value, size_t value_size) {
    if (!rtree || !point || point->dimensions != rtree->dimensions) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    rtree_rect_t rect;
    rtree_rect_from_point(&rect, point);
    
    return rtree_insert(rtree, &rect, value, value_size);
}

index_result_t rtree_search_rect(rtree_index_t* rtree, const rtree_rect_t* rect,
                                index_search_result_t* result) {
    if (!rtree || !rect || !result || rect->dimensions != rtree->dimensions) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    pthread_rwlock_rdlock(&rtree->tree_lock);
    
    rtree->searches++;
    
    result->found = false;
    result->value = NULL;
    result->value_size = 0;
    result->record_id = 0;
    
    rtree_node_t* current = rtree->root;
    while (current) {
        pthread_rwlock_rdlock(&current->rwlock);
        
        bool found_intersection = false;
        rtree_node_t* next = NULL;
        
        for (uint32_t i = 0; i < current->entry_count; i++) {
            if (rtree_rect_intersects(&current->entries[i].mbr, rect)) {
                if (current->type == RTREE_NODE_LEAF) {
                    result->found = true;
                    result->value = current->entries[i].value;
                    result->value_size = current->entries[i].value_size;
                    result->record_id = current->entries[i].record_id;
                    found_intersection = true;
                    break;
                } else {
                    next = current->entries[i].child;
                    found_intersection = true;
                    break;
                }
            }
        }
        
        pthread_rwlock_unlock(&current->rwlock);
        
        if (current->type == RTREE_NODE_LEAF || !found_intersection) {
            break;
        }
        
        current = next;
    }
    
    pthread_rwlock_unlock(&rtree->tree_lock);
    
    return result->found ? INDEX_SUCCESS : INDEX_ERROR_KEY_NOT_FOUND;
}

index_result_t rtree_search_point(rtree_index_t* rtree, const rtree_point_t* point,
                                 index_search_result_t* result) {
    if (!rtree || !point || point->dimensions != rtree->dimensions) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    rtree_rect_t rect;
    rtree_rect_from_point(&rect, point);
    
    return rtree_search_rect(rtree, &rect, result);
}

index_result_t rtree_delete(rtree_index_t* rtree, const rtree_rect_t* rect) {
    if (!rtree || !rect || rect->dimensions != rtree->dimensions) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    pthread_rwlock_wrlock(&rtree->tree_lock);
    
    rtree->deletes++;
    
    rtree_node_t* leaf = rtree_find_leaf(rtree, rect);
    if (!leaf) {
        pthread_rwlock_unlock(&rtree->tree_lock);
        return INDEX_ERROR_KEY_NOT_FOUND;
    }
    
    pthread_rwlock_wrlock(&leaf->rwlock);
    
    uint32_t delete_index = UINT32_MAX;
    for (uint32_t i = 0; i < leaf->entry_count; i++) {
        if (rtree_rect_intersects(&leaf->entries[i].mbr, rect)) {
            delete_index = i;
            break;
        }
    }
    
    pthread_rwlock_unlock(&leaf->rwlock);
    
    if (delete_index == UINT32_MAX) {
        pthread_rwlock_unlock(&rtree->tree_lock);
        return INDEX_ERROR_KEY_NOT_FOUND;
    }
    
    index_result_t result = rtree_node_delete_entry(leaf, delete_index);
    
    if (result == INDEX_SUCCESS) {
        rtree->total_entries--;
    }
    
    pthread_rwlock_unlock(&rtree->tree_lock);
    return result;
}

index_result_t rtree_delete_point(rtree_index_t* rtree, const rtree_point_t* point) {
    if (!rtree || !point || point->dimensions != rtree->dimensions) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    rtree_rect_t rect;
    rtree_rect_from_point(&rect, point);
    
    return rtree_delete(rtree, &rect);
}

rtree_iterator_t* rtree_range_scan_rect(rtree_index_t* rtree,
                                       const rtree_rect_t* rect, bool forward) {
    if (!rtree) return NULL;
    
    rtree_iterator_t* iter = mm_alloc(rtree->memory_mgr, sizeof(rtree_iterator_t),
                                     MEM_TYPE_INDEX_BUFFER);
    if (!iter) return NULL;
    
    memset(iter, 0, sizeof(rtree_iterator_t));
    iter->index = rtree;
    iter->forward = forward;
    iter->is_valid = false;
    iter->stack_depth = 0;
    
    if (rect) {
        iter->query_rect = *rect;
        iter->use_query_rect = true;
    } else {
        iter->use_query_rect = false;
    }
    
    if (rtree->root && rtree->root->entry_count > 0) {
        iter->stack[0].node = rtree->root;
        iter->stack[0].entry_index = 0;
        iter->stack_depth = 1;
        iter->is_valid = true;
    }
    
    return iter;
}

bool rtree_iterator_valid(rtree_iterator_t* iter) {
    return iter && iter->is_valid && iter->stack_depth > 0;
}

index_result_t rtree_iterator_next(rtree_iterator_t* iter) {
    if (!iter || !iter->is_valid || iter->stack_depth == 0) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    while (iter->stack_depth > 0) {
        rtree_node_t* current_node = iter->stack[iter->stack_depth - 1].node;
        uint32_t* entry_index = &iter->stack[iter->stack_depth - 1].entry_index;
        
        if (*entry_index >= current_node->entry_count) {
            iter->stack_depth--;
            continue;
        }
        
        rtree_entry_t* entry = &current_node->entries[*entry_index];
        (*entry_index)++;
        
        if (iter->use_query_rect && !rtree_rect_intersects(&entry->mbr, &iter->query_rect)) {
            continue;
        }
        
        if (current_node->type == RTREE_NODE_LEAF) {
            iter->current_node = current_node;
            iter->current_entry = *entry_index - 1;
            return INDEX_SUCCESS;
        } else if (entry->child && iter->stack_depth < 32) {
            iter->stack[iter->stack_depth].node = entry->child;
            iter->stack[iter->stack_depth].entry_index = 0;
            iter->stack_depth++;
        }
    }
    
    iter->is_valid = false;
    return INDEX_SUCCESS;
}

index_result_t rtree_iterator_current(rtree_iterator_t* iter,
                                     rtree_rect_t* rect, void** value, size_t* value_size) {
    if (!iter || !iter->is_valid || !iter->current_node ||
        iter->current_entry >= iter->current_node->entry_count) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    rtree_entry_t* entry = &iter->current_node->entries[iter->current_entry];
    
    if (rect) *rect = entry->mbr;
    if (value) *value = entry->value;
    if (value_size) *value_size = entry->value_size;
    
    return INDEX_SUCCESS;
}

void rtree_iterator_destroy(rtree_iterator_t* iter) {
    if (!iter) return;
    
    mm_free(iter->index->memory_mgr, iter);
}

index_result_t rtree_bulk_insert(rtree_index_t* rtree,
                                const rtree_rect_t* rects,
                                const void** values, size_t* value_sizes,
                                size_t count) {
    if (!rtree || !rects || count == 0) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    for (size_t i = 0; i < count; i++) {
        const void* value = values ? values[i] : NULL;
        size_t value_size = value_sizes ? value_sizes[i] : 0;
        
        index_result_t result = rtree_insert(rtree, &rects[i], value, value_size);
        if (result != INDEX_SUCCESS && result != INDEX_ERROR_KEY_EXISTS) {
            return result;
        }
    }
    
    return INDEX_SUCCESS;
}

size_t rtree_range_delete_rect(rtree_index_t* rtree, const rtree_rect_t* rect) {
    if (!rtree || !rect) return 0;
    
    rtree_iterator_t* iter = rtree_range_scan_rect(rtree, rect, true);
    if (!iter) return 0;
    
    size_t deleted_count = 0;
    
    while (rtree_iterator_valid(iter)) {
        rtree_rect_t current_rect;
        
        if (rtree_iterator_current(iter, &current_rect, NULL, NULL) == INDEX_SUCCESS) {
            if (rtree_delete(rtree, &current_rect) == INDEX_SUCCESS) {
                deleted_count++;
            }
        }
        
        rtree_iterator_next(iter);
    }
    
    rtree_iterator_destroy(iter);
    return deleted_count;
}

index_result_t rtree_clear(rtree_index_t* rtree) {
    if (!rtree) return INDEX_ERROR_INVALID_PARAM;
    
    pthread_rwlock_wrlock(&rtree->tree_lock);
    
    if (rtree->root) {
        rtree_node_destroy(rtree->root);
    }
    
    rtree->root = rtree_node_create(rtree->memory_mgr, RTREE_NODE_LEAF,
                                   rtree->max_entries, rtree->dimensions);
    if (!rtree->root) {
        pthread_rwlock_unlock(&rtree->tree_lock);
        return INDEX_ERROR_OUT_OF_MEMORY;
    }
    
    rtree->root->is_root = true;
    rtree->height = 1;
    rtree->total_entries = 0;
    
    pthread_rwlock_unlock(&rtree->tree_lock);
    return INDEX_SUCCESS;
}

index_result_t rtree_rebuild(rtree_index_t* rtree) {
    return rtree_clear(rtree);
}

bool rtree_validate(rtree_index_t* rtree) {
    if (!rtree || !rtree->root) return false;
    
    pthread_rwlock_rdlock(&rtree->tree_lock);
    
    bool valid = rtree->root->is_root && rtree->height >= 1;
    
    pthread_rwlock_unlock(&rtree->tree_lock);
    return valid;
}

void rtree_get_stats(rtree_index_t* rtree, index_stats_t* stats) {
    if (!rtree || !stats) return;
    
    pthread_rwlock_rdlock(&rtree->tree_lock);
    
    memset(stats, 0, sizeof(index_stats_t));
    stats->total_keys = rtree->total_entries;
    stats->searches = rtree->searches;
    stats->inserts = rtree->inserts;
    stats->deletes = rtree->deletes;
    stats->avg_depth = (double)rtree->height;
    
    pthread_rwlock_unlock(&rtree->tree_lock);
}

void rtree_print_rect(const rtree_rect_t* rect) {
    if (!rect) return;
    
    printf("Rect[%dd]: ", rect->dimensions);
    for (uint8_t i = 0; i < rect->dimensions; i++) {
        printf("(%.2f,%.2f)", rect->min[i], rect->max[i]);
        if (i < rect->dimensions - 1) printf(",");
    }
}

void rtree_print_point(const rtree_point_t* point) {
    if (!point) return;
    
    printf("Point[%dd]: (", point->dimensions);
    for (uint8_t i = 0; i < point->dimensions; i++) {
        printf("%.2f", point->coords[i]);
        if (i < point->dimensions - 1) printf(",");
    }
    printf(")");
}

void rtree_print_node(rtree_node_t* node, int level) {
    if (!node) return;
    
    pthread_rwlock_rdlock(&node->rwlock);
    
    for (int i = 0; i < level; i++) {
        printf("  ");
    }
    
    printf("Node[%s, entries=%u]: ",
           node->type == RTREE_NODE_LEAF ? "LEAF" : "INTERNAL",
           node->entry_count);
    rtree_print_rect(&node->mbr);
    printf("\n");
    
    for (uint32_t i = 0; i < node->entry_count; i++) {
        for (int j = 0; j < level + 1; j++) {
            printf("  ");
        }
        printf("Entry[%u]: ", i);
        rtree_print_rect(&node->entries[i].mbr);
        printf("\n");
        
        if (node->type == RTREE_NODE_INTERNAL && node->entries[i].child) {
            rtree_print_node(node->entries[i].child, level + 2);
        }
    }
    
    pthread_rwlock_unlock(&node->rwlock);
}

void rtree_print_tree(rtree_index_t* rtree) {
    if (!rtree || !rtree->root) return;
    
    printf("R-Tree (%ud, height=%u, entries=%llu):\n",
           rtree->dimensions, rtree->height, (unsigned long long)rtree->total_entries);
    rtree_print_node(rtree->root, 0);
}

index_result_t rtree_key_to_rect(const void* key, size_t key_size, rtree_rect_t* rect) {
    if (!key || !rect || key_size < sizeof(rtree_rect_t)) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    memcpy(rect, key, sizeof(rtree_rect_t));
    return INDEX_SUCCESS;
}

index_result_t rtree_key_to_point(const void* key, size_t key_size, rtree_point_t* point) {
    if (!key || !point || key_size < sizeof(rtree_point_t)) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    memcpy(point, key, sizeof(rtree_point_t));
    return INDEX_SUCCESS;
}

index_result_t rtree_rect_to_key(const rtree_rect_t* rect, void** key, size_t* key_size,
                                memory_manager_t* memory_mgr) {
    if (!rect || !key || !key_size || !memory_mgr) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    *key = mm_alloc(memory_mgr, sizeof(rtree_rect_t), MEM_TYPE_INDEX_BUFFER);
    if (!*key) return INDEX_ERROR_OUT_OF_MEMORY;
    
    memcpy(*key, rect, sizeof(rtree_rect_t));
    *key_size = sizeof(rtree_rect_t);
    
    return INDEX_SUCCESS;
}

index_result_t rtree_point_to_key(const rtree_point_t* point, void** key, size_t* key_size,
                                 memory_manager_t* memory_mgr) {
    if (!point || !key || !key_size || !memory_mgr) {
        return INDEX_ERROR_INVALID_PARAM;
    }
    
    *key = mm_alloc(memory_mgr, sizeof(rtree_point_t), MEM_TYPE_INDEX_BUFFER);
    if (!*key) return INDEX_ERROR_OUT_OF_MEMORY;
    
    memcpy(*key, point, sizeof(rtree_point_t));
    *key_size = sizeof(rtree_point_t);
    
    return INDEX_SUCCESS;
}

// Interface implementation functions

static index_result_t rtree_interface_insert(index_instance_t* index,
                                            const void* key, size_t key_size,
                                            const void* value, size_t value_size) {
    if (!index || !index->index_data) return INDEX_ERROR_INVALID_PARAM;
    rtree_index_t* rtree = (rtree_index_t*)index->index_data;
    
    rtree_rect_t rect;
    index_result_t result = rtree_key_to_rect(key, key_size, &rect);
    if (result != INDEX_SUCCESS) return result;
    
    return rtree_insert(rtree, &rect, value, value_size);
}

static index_result_t rtree_interface_delete(index_instance_t* index,
                                            const void* key, size_t key_size) {
    if (!index || !index->index_data) return INDEX_ERROR_INVALID_PARAM;
    rtree_index_t* rtree = (rtree_index_t*)index->index_data;
    
    rtree_rect_t rect;
    index_result_t result = rtree_key_to_rect(key, key_size, &rect);
    if (result != INDEX_SUCCESS) return result;
    
    return rtree_delete(rtree, &rect);
}

static index_result_t rtree_interface_update(index_instance_t* index,
                                            const void* key, size_t key_size,
                                            const void* value, size_t value_size) {
    index_result_t delete_result = rtree_interface_delete(index, key, key_size);
    if (delete_result != INDEX_SUCCESS) {
        return delete_result;
    }
    
    return rtree_interface_insert(index, key, key_size, value, value_size);
}

static index_result_t rtree_interface_search(index_instance_t* index,
                                            const void* key, size_t key_size,
                                            index_search_result_t* result) {
    if (!index || !index->index_data) return INDEX_ERROR_INVALID_PARAM;
    rtree_index_t* rtree = (rtree_index_t*)index->index_data;
    
    rtree_rect_t rect;
    index_result_t conv_result = rtree_key_to_rect(key, key_size, &rect);
    if (conv_result != INDEX_SUCCESS) return conv_result;
    
    return rtree_search_rect(rtree, &rect, result);
}

static index_iterator_t* rtree_interface_range_scan(index_instance_t* index,
                                                   const void* start_key, size_t start_key_size,
                                                   const void* end_key, size_t end_key_size,
                                                   bool forward) {
    if (!index || !index->index_data) return NULL;
    rtree_index_t* rtree = (rtree_index_t*)index->index_data;
    
    // Note: end_key parameters are kept for interface compatibility
    // but not used in R-tree range scans
    (void)end_key;
    (void)end_key_size;
    
    rtree_rect_t* rect = NULL;
    rtree_rect_t query_rect;
    
    if (start_key && start_key_size > 0) {
        if (rtree_key_to_rect(start_key, start_key_size, &query_rect) == INDEX_SUCCESS) {
            rect = &query_rect;
        }
    }
    
    rtree_iterator_t* rtree_iter = rtree_range_scan_rect(rtree, rect, forward);
    if (!rtree_iter) return NULL;
    
    index_iterator_t* iter = mm_alloc(rtree->memory_mgr,
                                     sizeof(index_iterator_t),
                                     MEM_TYPE_INDEX_BUFFER);
    if (!iter) {
        rtree_iterator_destroy(rtree_iter);
        return NULL;
    }
    
    memset(iter, 0, sizeof(index_iterator_t));
    iter->index = index;
    iter->internal_state = rtree_iter;
    iter->is_valid = rtree_iterator_valid(rtree_iter);
    iter->forward = forward;
    
    return iter;
}

static bool rtree_interface_iterator_valid(index_iterator_t* iter) {
    if (!iter || !iter->internal_state) return false;
    rtree_iterator_t* rtree_iter = (rtree_iterator_t*)iter->internal_state;
    return rtree_iterator_valid(rtree_iter);
}

static index_result_t rtree_interface_iterator_next(index_iterator_t* iter) {
    if (!iter || !iter->internal_state) return INDEX_ERROR_INVALID_PARAM;
    rtree_iterator_t* rtree_iter = (rtree_iterator_t*)iter->internal_state;
    return rtree_iterator_next(rtree_iter);
}

static index_result_t rtree_interface_iterator_current(index_iterator_t* iter,
                                                      void** key, size_t* key_size,
                                                      void** value, size_t* value_size) {
    if (!iter || !iter->internal_state) return INDEX_ERROR_INVALID_PARAM;
    rtree_iterator_t* rtree_iter = (rtree_iterator_t*)iter->internal_state;
    
    rtree_rect_t rect;
    void* val;
    size_t val_size;
    
    index_result_t result = rtree_iterator_current(rtree_iter, &rect, &val, &val_size);
    if (result != INDEX_SUCCESS) return result;
    
    if (key && key_size) {
        rtree_index_t* rtree = rtree_iter->index;
        return rtree_rect_to_key(&rect, key, key_size, rtree->memory_mgr);
    }
    
    if (value) *value = val;
    if (value_size) *value_size = val_size;
    
    return INDEX_SUCCESS;
}

static void rtree_interface_iterator_destroy(index_iterator_t* iter) {
    if (!iter) return;
    
    if (iter->internal_state) {
        rtree_iterator_t* rtree_iter = (rtree_iterator_t*)iter->internal_state;
        rtree_iterator_destroy(rtree_iter);
    }
    
    if (iter->index && iter->index->index_data) {
        rtree_index_t* rtree = (rtree_index_t*)iter->index->index_data;
        mm_free(rtree->memory_mgr, iter);
    }
}

static index_result_t rtree_interface_bulk_insert(index_instance_t* index,
                                                 const void** keys, size_t* key_sizes,
                                                 const void** values, size_t* value_sizes,
                                                 size_t count) {
    if (!index || !index->index_data || !keys) return INDEX_ERROR_INVALID_PARAM;
    
    for (size_t i = 0; i < count; i++) {
        const void* value = values ? values[i] : NULL;
        size_t value_size = value_sizes ? value_sizes[i] : 0;
        
        index_result_t result = rtree_interface_insert(index, keys[i], key_sizes[i],
                                                      value, value_size);
        if (result != INDEX_SUCCESS && result != INDEX_ERROR_KEY_EXISTS) {
            return result;
        }
    }
    
    return INDEX_SUCCESS;
}

static size_t rtree_interface_range_delete(index_instance_t* index,
                                          const void* start_key, size_t start_key_size,
                                          const void* end_key, size_t end_key_size) {
    if (!index || !index->index_data) return 0;
    rtree_index_t* rtree = (rtree_index_t*)index->index_data;
    
    // Note: Only start_key is used for spatial deletion
    (void)end_key;
    (void)end_key_size;
    
    rtree_rect_t rect;
    if (rtree_key_to_rect(start_key, start_key_size, &rect) != INDEX_SUCCESS) {
        return 0;
    }
    
    return rtree_range_delete_rect(rtree, &rect);
}

static index_result_t rtree_interface_clear(index_instance_t* index) {
    if (!index || !index->index_data) return INDEX_ERROR_INVALID_PARAM;
    rtree_index_t* rtree = (rtree_index_t*)index->index_data;
    return rtree_clear(rtree);
}

static index_result_t rtree_interface_rebuild(index_instance_t* index) {
    if (!index || !index->index_data) return INDEX_ERROR_INVALID_PARAM;
    rtree_index_t* rtree = (rtree_index_t*)index->index_data;
    return rtree_rebuild(rtree);
}

static void rtree_interface_destroy(index_instance_t* index) {
    if (!index || !index->index_data) return;
    rtree_index_t* rtree = (rtree_index_t*)index->index_data;
    rtree_destroy(rtree);
    index->index_data = NULL;
}

static void rtree_interface_get_stats(index_instance_t* index, index_stats_t* stats) {
    if (!index || !index->index_data || !stats) return;
    rtree_index_t* rtree = (rtree_index_t*)index->index_data;
    rtree_get_stats(rtree, stats);
}

static bool rtree_interface_validate(index_instance_t* index) {
    if (!index || !index->index_data) return false;
    rtree_index_t* rtree = (rtree_index_t*)index->index_data;
    return rtree_validate(rtree);
}

static index_result_t rtree_interface_set_config(index_instance_t* index,
                                                const index_config_t* config) {
    if (!index || !config) return INDEX_ERROR_INVALID_PARAM;
    
    memcpy(&index->config, config, sizeof(index_config_t));
    return INDEX_SUCCESS;
}

static void rtree_interface_get_config(index_instance_t* index, index_config_t* config) {
    if (!index || !config) return;
    memcpy(config, &index->config, sizeof(index_config_t));
}

index_interface_t* rtree_interface_create(void) {
    index_interface_t* interface = malloc(sizeof(index_interface_t));
    if (!interface) return NULL;
    
    memset(interface, 0, sizeof(index_interface_t));
    
    interface->insert = rtree_interface_insert;
    interface->delete = rtree_interface_delete;
    interface->update = rtree_interface_update;
    interface->search = rtree_interface_search;
    interface->range_scan = rtree_interface_range_scan;
    interface->iterator_valid = rtree_interface_iterator_valid;
    interface->iterator_next = rtree_interface_iterator_next;
    interface->iterator_current = rtree_interface_iterator_current;
    interface->iterator_destroy = rtree_interface_iterator_destroy;
    interface->bulk_insert = rtree_interface_bulk_insert;
    interface->range_delete = rtree_interface_range_delete;
    interface->clear = rtree_interface_clear;
    interface->rebuild = rtree_interface_rebuild;
    interface->destroy = rtree_interface_destroy;
    interface->get_stats = rtree_interface_get_stats;
    interface->validate = rtree_interface_validate;
    interface->set_config = rtree_interface_set_config;
    interface->get_config = rtree_interface_get_config;
    
    return interface;
}